package nowCoder;

/**
 * Created by Ghost on 2015/3/25.
 * Given two sorted integer arrays A and B, merge B into A as one sorted array.
 Note:
 You may assume that A has enough space to hold additional elements from B.
 The number of elements initialized in A and B are m and n respectively.
 */
public class Merge_sorted_array {
    public void merge(int A[], int m, int B[], int n) {
        int startA=m-1,startB=n-1;
        int finalDestination = m+n-1;
        while(startA>=0 && startB>=0){
            if(A[startA]>B[startB]){
                A[finalDestination] = A[startA];
                startA--;
                finalDestination--;
            } else{
                A[finalDestination] = B[startB];
                startB--;
                finalDestination--;
            }
        }

        if(startA<0 && startB>=0){
            for(;startB>=0;startB--,finalDestination--)
                A[finalDestination] = B[startB];
        } else{
            for(;startA>=0;startA--,finalDestination--)
                A[finalDestination] = A[startA];
        }

    }

    public static void main(String[] args){
        Merge_sorted_array merge_sorted_array = new Merge_sorted_array();
        int[] A = {1,3,4,8,8};
        int[] B = {2};
        merge_sorted_array.merge(A,4,B,1);
        for(int i=0;i<5;i++)
            System.out.println(A[i]);
    }
}
